package com.zjj.algorithm.learning.niuke;

import java.util.*;
import java.util.stream.Collectors;

/**
 * @author zjj_admin
 * @date 2023/2/10 20:57
 */
public class Exam3 {

    private static int res = 0;

    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);
        String s1 = scanner.nextLine();
        String[] split1 = s1.split(" ");
        int pointNum = Integer.parseInt(split1[0]);
        int bianNum = Integer.parseInt(split1[1]);
        int i = 0;
        String data;
        int point1;
        int point2;
        int[][] graph = new int[pointNum][pointNum];
        while (i < bianNum) {
            data = scanner.nextLine();
            String[] datas = data.split(" ");
            point1 = Integer.parseInt(datas[0]);
            point2 = Integer.parseInt(datas[1]);
            graph[point1][point2] = 1;
            graph[point2][point1] = 1;
            i++;
        }
        res = 0;
        //在开始全部图和一个都不涂
        res = pointNum + 1;
        List<Set<Integer>> list1 = new ArrayList<>();
        Set<Integer> allPoint = new HashSet<>();
        for (int j = 0; j < pointNum; j++) {
            Set<Integer> list3 = new HashSet<>();
            list3.add(j);
            list1.add(list3);
            allPoint.add(j);
        }
        List<Set<Integer>> resList = other(graph, list1, allPoint);
        while (resList.size() > 0) {
            resList = other(graph, resList, allPoint);
        }
        System.out.println(res);
    }

    private static List<Set<Integer>> other(int[][] graph, List<Set<Integer>> list1, Set<Integer> allPoint) {
        List<Set<Integer>> resList = new ArrayList<>();
        for (Set<Integer> items : list1) {
            Set<Integer> set1 = new HashSet<>(items);
            List<Integer> other = allPoint.stream().filter(it -> !items.contains(it)).collect(Collectors.toList());
            for (Integer oth : other) {
                boolean repeat = isRepeat(resList, items, oth);
                boolean available = isAvailable(graph, items, oth);
                if (repeat && available) {
                    res++;
                    set1.add(oth);
                    resList.add(set1);
                }
            }
        }
        return resList;
    }

    /**
     * 判断是否重复
     *
     * @param resList
     * @param items
     * @param oth
     * @return
     */
    private static boolean isRepeat(List<Set<Integer>> resList, Set<Integer> items, int oth) {
        Set<Integer> set = new HashSet<>(items);
        set.add(oth);
        for (Set<Integer> num : resList) {
            if (set.equals(num)) {
                return false;
            }
        }
        return true;
    }

    /**
     * 判断添加一个是不是红黑树
     *
     * @param graph
     * @param items
     * @param other
     * @return
     */
    public static boolean isAvailable(int[][] graph, Set<Integer> items, Integer other) {
        for (Integer item : items) {
            if (graph[item][other] == 1 || graph[other][item] == 1) {
                return false;
            }
        }
        return true;
    }
}
